#include <gtest/gtest.h>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace ::std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target);
	vector<int> findValue(vector<int>& nums, int target);
	vector<int> findIndex(vector<int>& nums, int lhs, int rhs);
};

vector<int> Solution::twoSum(vector<int>& nums, int target) {
	vector<int> Value = findValue(nums, target);
	return findIndex(nums, Value[0], Value[1]);
}

vector<int> Solution::findValue(vector<int>& nums, int target) {
    int front = 0, back = nums.size() - 1;
	vector<int> alpha(nums);
	sort(alpha.begin(), alpha.end());
	for(; front < back; front++) { // 从前往后遍历
		int balance = target - alpha[front];
		// 从后往前遍历，大于现有差额的元素不可能成为解直接跳过，下次不再遍历
		while(front < back && alpha[back] > balance) back--; 
		if(alpha[back] == balance) return {alpha[front], alpha[back]};
	}
	return {};
}

vector<int> Solution::findIndex(vector<int>& nums, int lhs, int rhs) {
	int indexA = -1, indexB = -1;
	bool findFirst = false;
	for(auto n : nums) {
		findFirst ? (indexB++) : (indexA++, indexB++);
		if((n == lhs) || (n == rhs)) {
			findFirst = true;
			if(n == lhs) lhs = INT_MAX;
			else if(n == rhs) rhs = INT_MAX;
		}
		if(INT_MAX == rhs && INT_MAX == lhs) break;
	}
	return {indexA, indexB};
}

class TwoSumCheck : public ::testing::Test {
public:
	class Solution solution;
};

TEST_F(TwoSumCheck, testFindValue) {
	vector<int> nums = {2, 3, 4, 5, 6, 10};
	EXPECT_TRUE(vector<int>({2, 3}) == solution.findValue(nums, 5));
}

TEST_F(TwoSumCheck, testFindIndex) {
	vector<int> nums = {10, 2, 3, 4, 5, 6};
	EXPECT_TRUE(vector<int>({1, 2}) == solution.findIndex(nums, 2, 3));
}

TEST_F(TwoSumCheck, testTwoSum_1) {
	vector<int> nums = {10, 2, 3, 4, 5, 6};
	EXPECT_TRUE((vector<int>{1, 2}) == (solution.twoSum(nums, 5)));
}

TEST_F(TwoSumCheck, testTwoSum_2) {
	vector<int> nums({7, 2, 11, 15});
	EXPECT_TRUE(vector<int>({0, 1}) == solution.twoSum(nums, 9));
}

TEST_F(TwoSumCheck, testTwoSum_3) {
	vector<int> nums({3, 3, 4});
	EXPECT_TRUE(vector<int>({0, 1}) == solution.twoSum(nums, 6));
}

TEST_F(TwoSumCheck, testTwoSum_4) {
	vector<int> nums({0, 3, -3, 4, -1});
	EXPECT_TRUE(vector<int>({0, 4}) == solution.twoSum(nums, -1));
}

int main() {
	::testing::InitGoogleTest();
	return RUN_ALL_TESTS();
}
